public class MergeSort {
    public void mergeSort(int []array){
        mergeSortFunc(array,0,array.length-1);
    }

    private void mergeSortFunc(int []array, int left, int right){//实现递归的函数
        if(left==right)return;//当分割到只有一个时结束分割
        int mid=(right+left)/2;
        mergeSortFunc(array,left,mid);//左侧
        mergeSortFunc(array,mid+1,right);//右侧
        //合并  将左右两侧的数组进行合并
        merge(array,left,right,mid);
    }

    private void merge(int[]array,int left,int right,int mid){//进行顺序合并的函数
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int []index=new int[right-left+1];
        int i=0;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                index[i++]=array[s1++];
            }else{
                index[i++]=array[s2++];
            }
        }
        while(s1<=e1){
            index[i++]=array[s1++];
        }
        while(s2<=e2){
            index[i++]=array[s2++];
        }
        for(int j=0;j<index.length;j++){//array[j+left]就是在真实数组中的位置,即从left下标的位置开始
            array[j+left]=index[j];
        }
    }
    public void nonRecursiveMergeSort(int []array){// 用gap标记当前的合并的一个组合的数据元素个数
        int gap=1;
        while(gap<=array.length){
            for (int i = 0; i <array.length ; i+=gap*2) {//i从0开始进行每组的遍历
                int left=i;
                int mid=i+gap-1;
                if(mid>=array.length){
                    mid= array.length-1;
                }
                int right=i+gap*2-1;
                if(right>=array.length){
                    right= array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap*=2;//回到上一组
        }
    }
}
